package dichotomy.isprefectnum;
/**
 * @Date 2020/1/23
 * @author 王光浩
 * @Need 给出一个整数，判断该数是否是一个完全平方数，如果是则返回true，否则返回false。
 * @Thinking 二分法。使用第一种二分法
 *           复杂度分析：时间复杂度O（logn），空间复杂度O（1）
 * @Improving 当num大于2时，如果num是一个完全平方数，则开方后所得值小于等于num/2。所以右边界完全可以缩小。
 */
public class MyMethodTwo {
	public boolean isPerfectSquare(int num) {
		if(num<2)return true;
		int later=num/2;
		int previous=2;
		int mid;
		long tem=num;
		while(later>=previous) {
			mid=previous+(later-previous)/2;
			if((long)mid*mid==tem)return true;
			if((long)mid*mid<tem)previous=mid+1;
			else later=mid-1;
		}
		return false;
	}

}
